1. Field of the Invention
The present invention relates to a distributed/opportunistic scheduling method for acquiring a multi-user diversity gain in a wireless local area network (WLAN), and a more particularly to a distributed/opportunistic scheduling method for acquiring a multi-user diversity gain in a WLAN, which uses a multi-user diversity technique in a WLAN or Ad-hoc network environment to improve overall process efficiency of the WLAN or Ad-hoc network, thereby increasing throughput as well as fairly assigning a radio-channel access time to a plurality of receivers.
2. Description of the Related Art
WLANs (Wireless Local Area Networks), which provide flexible impromptu accesses to the Internet, have been widely deployed for the last several years.
The establishment of the IEEE 802.11 WLAN standard has propelled the explosive development and deployment of WLAN products. At the beginning, the IEEE WLAN standard started with 1 or 2 Mbps WLAN specifications. Later the standard body established the 802.11b technology that supports two supplementary data rates of 5.5 Mbps and 11 Mbps. WLAN technologies advanced further and 802.11a or 802.11g devices, which provide up to 54 Mbps data rate, have gained wide popularity in recent years. The IEEE 802.11 standard committee is currently working on the 802.11n specifications for transmission rates up to 600 Mbps.
Like many other modern wireless communication techniques, the IEEE 802.11 WLANs support the multi-rate capability by adopting rate-dependent modulation schemes and coding rates. Denser modulation schemes or higher coding rates increase data bits per symbol, but signals become more vulnerable to interference or noise. A sender should select appropriate transmission rates based on receiver's current channel condition. The selection of proper data rates is called rate adaptation and many rate adaptation algorithms have been proposed.
Automatic Rate Fallback (ARF) is implemented in many commercial wireless devices due to its simplicity. On the other hand, Receiver Based Auto Rate (RBAR) will be included in several standards such as IEEE 802.11n. Note that the rate adaptation problem optimizes the transmissions on a single time-varying wireless link.
Multiple time-varying wireless links provide the opportunities to further improve the performance of the systems. Each wireless link quality independently fluctuates both in a short-term scale (small-scale fading) and in a long-term scale (large-scale propagation). In this document, we focus on small-scale fading.
Rayleigh and Ricean distributions describe the time-varying characteristics of a small-scale flat fading signal in the outdoor and indoor environments, respectively. Suppose that a sender has packets to send to several receivers each of which experiences independent small-scale fading. Because we can adjust transmission rates based on receiver's channel quality, a sender may be able to improve its throughput by scheduling receivers which happened to be in good channel conditions. The scheduling algorithms, which exploit the dynamic fluctuation of receivers' channel qualities or multi-user diversity, are called opportunistic scheduling algorithms.
Information on receivers' channel states is essential for implementing opportunistic scheduling. In 1×EVDO, a Base Station (BS) adjusts transmission rates according to the channel conditions of the Mobile Hosts (MHs). The BS broadcasts a pilot signal periodically at full power, and each MH measures the Carrier to Interference ratio (C/I) of the pilot signal. This channel state information, in the form of a data rate, is reported to the BS via the Data Rate Control (DRC) channel every 1.67 ms. The requested data rate is the highest possible sending rate from the BS to the MH for the current channel condition. 1×EVDO adopts the Proportional Fair (PF) scheduler as a scheduling algorithm at BS. The PF scheduler guarantees temporal fairness using the relative channel quality as a criterion in selecting receivers. That is, the PF scheduler selects the MH with the largest value of DRCi(t)/Ri(t), where Ri(t) is the average transmission rate and DRCi(t) is the requested data rate of user i at slot time t.
The PF scheduler updates Ri(t) in each slot according to the following equation,Ri(t+1)=(1−1/tc)Ri(t)+1/tc*DRCi(t)*δi,  [Equation 1]
where the parameter tc is the time constant of a low pass filter. δi is set to 1 if user i is served at a time slot t, otherwise it is set to 0. It has been shown that PF scheduling realizes high channel efficiency while ensuring temporal fairness even if the station's channel quality statistics are unknown.
Let us examine the rate adaptation schemes proposed for WLANs. Two representative rate adaptation schemes have been proposed: ARF (Automatic Rate Fallback) and RBAR (Receiver Based Auto Rate).
With ARF, if two consecutive transmissions to a receiver fail, a sender reduces the transmission rate to the receiver by one level. On the other hand, the sender increases the rate to the next higher level in the case that ten consecutive transmissions to the receiver are all successful. That is, ARF adjusts data rates in a trial-and-error manner without explicit channel information. Certainly, we can perform more precise adjustments if the channel information is explicitly provided to the sender.
RBAR uses the RTS/CTS handshake for the delivery of channel information. Receiving an RTS from a sender, a receiver measures the signal quality of the RTS and informs the sender of the optimal data rate by specifying it in a CTS frame.
It is more complex to adopt opportunistic scheduling in WLANs than cellular network systems. As explained before, cellular network systems such as 1×EVDO have an intrinsic channel information report mechanism. The IEEE 802.11 WLANs do not support a mechanism that collects receiver channel information. We must first devise channel probing mechanism to employ opportunistic scheduling in WLANs.
In spite of the difficulty of collecting receivers' channel quality information, two opportunistic scheduling algorithms for WLANs have been proposed recently: MAD (Medium Access Diversity) and OSMA (Opportunistic packet Scheduling and Media Access control).
Both schemes employ the RTS (Request-to-Send)/CTS (Clear-to-Send) handshake with modifications for channel probing.
In MAD, a sender selects a few candidate receivers among all active receivers and multicasts an RTS frame to the selected receivers. The sender explicitly specifies the selected candidates by recording their addresses in the RTS frame. Each probed receiver reports its channel condition to the sender via a CTS frame. To avoid CTS collisions, the receivers transmit CTS frames according to the order specified in the RTS frame. Based on the reported channel information, the sender selects the most appropriate receiver based on various criteria. Let us examine the channel probing procedure of MAD. A sender, S, selects k candidates among N receivers and multicasts an RTS frame to the selected candidates. Assume that the ordering of candidate receivers be R1, R2, . . . , Rk. The receivers transmit CTS frames in the specified order adding SIFS delays between two consecutive CTS frames. The number of probed candidates, k, is an important parameter that decides the multi-user diversity gains and the channel probing overheads of MAD. The overheads and the gains of MAD increase as k increases. An extensive sensitivity study showed that the optimal number is three.
OSMA is another opportunistic scheduling protocol designed for WLANs. Like MAD, a sender selects candidate receivers and transmits a channel probing message to the candidates. The differences are in the CTS response phase. While all selected candidates transmit CTS frames in MAD, only receivers whose channel qualities are better than a certain threshold reply with RTS frames after SIFS+(n−1)*SlotTime, where n is the priority of a receiver and SlotTime is one backoff slot time (i.e., 9 microseconds in IEEE 802.11a).
Another important difference is the early termination of the CTS response phase; the first CTS frame suppresses the following responses and terminates current channel probing. Again, we assume that k receivers, R1, R2, . . . , Rk, are selected in that order. R1, whose channel quality is lower than the threshold, keeps silent during its response period. R2, with a good channel quality, transmits a CTS frame after SIFS+SlotTime. Upon detecting the R2's response, the remaining receivers, R3, . . . , Rk, give up their responses. The sender transmits a DATA frame to R2 after SIFS. Two parameters, the number of candidate receivers and the threshold, interact in a rather subtle manner and determine the performance of OSMA. Wang and et. al. discovered that the adequate number of candidates is four.